package hashtable;

import java.util.HashMap;
/**
 * https://leetcode-cn.com/problems/two-sum/
 */
public class E1_TwoSum {
    /**
     * (查找表)官方解法
     * 时间复杂度 O(n) 时间复杂度 O(1)
     * key - nums[x]
     * value - nums[x]的下标x
     */
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        HashMap<Integer,Integer> hashMap = new HashMap<>(len-1);
        hashMap.put(nums[0], 0);

        for (int i = 1; i < len; i++) {
            int needNumber = target - nums[i];
            //利用containsKey()方法复杂度是 O(1) 的特性
            if (hashMap.containsKey(needNumber)) {
                return new int[] {i, hashMap.get(needNumber)};
            }
            hashMap.put(nums[i], i); 
        }
        return null;
    }
}
